package NewCode_OR36;

import stackAndQueue.Stack;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/29 16:04
 * 链表回文
 */
public class Solution {

    static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
        private static int sizeOf(ListNode head){
            int size = 0;
            for (ListNode cur  = head; cur != null; cur = cur.next) {
                size++;
            }
            return size;
        }
        private static ListNode middleOf(ListNode head,int size){
            for (int i = 0; i < size/2; i++) {
                head=head.next;
            }
            return head;
        }
        private static ListNode reverseOf(ListNode head){
            ListNode prev = null;
            ListNode cur = head;
            while (cur!=null){
                ListNode next= cur.next;

                cur.next = prev;
                prev = cur;
                cur = next;
            }
            return prev;
        }
        public boolean chkPalindrome(ListNode A) {
            // write code here
            //求size
            int size = sizeOf(A);
            //找到中间节点
            ListNode mid = middleOf( A,size);
            ListNode Rhead = reverseOf(mid);
            while (Rhead!=null && A!=null){
                if (Rhead.val != A.val){
                    return false;
                }
                Rhead = Rhead.next;
                A=A.next;
            }
            return true;
        }
    }
